package leetcode;

/**
 * @Classname LastRemaining_interview62
 * @Author happytaohaha
 * @Date 2020/3/30
 * @Description 面试题62. 圆圈中最后剩下的数字
 *  解体思路：归纳总结
 *  从f(1,m) = 0
 *  从f(2,m) = (0 + m)%2
 *  ...
 *  得： f(n,m) = (f(n-1,m) + m) % n
 *  把 n 和 m 分别代入题目给的数就会懂如何做
 */
public class LastRemaining_interview62 {

    public int lastRemaining(int n, int m) {
        return f(n,m);
    }

    private int f(int n, int m) {
        if (n == 1)
        { return 0;}
        return (m+ f(n-1,m))%n;
    }

    public static void main(String[] args) {

    }
}
